# 定义文法产生式
productions = {
    'E': ['TB'],
    'B': ['+TB', 'ε'],
    'T': ['FD'],
    'D': ['*FD', 'ε'],
    'F': ['(E)', 'i']
}

# First集
first = {
    'E': {'(', 'i'},
    'B': {'+', 'ε'},
    'T': {'(', 'i'},
    'D': {'*', 'ε'},
    'F': {'(', 'i'}
}

# Follow集
follow = {
    'E': {')', '#'},
    'B': {')', '#'},
    'T': {'+', ')', '#'},
    'D': {'+', ')', '#'},
    'F': {'*', '+', ')', '#'}
}

# 构造预测分析表
predict_table = {
    'E': {'(': 'TB', 'i': 'TB'},
    'B': {'+': '+TB', ')': 'ε', '#': 'ε'},
    'T': {'(': 'FD', 'i': 'FD'},
    'D': {'*': '*FD', '+': 'ε', ')': 'ε', '#': 'ε'},
    'F': {'(': '(E)', 'i': 'i'}
}


def ll1_analysis(input_str):
    stack = ['#', 'E']  # 初始化栈
    input_str += '#'  # 输入串末尾添加#
    ptr = 0  # 输入串指针
    print("步骤\t\t栈\t\t输入串\t\t动作")
    step = 1
    while stack:
        top = stack[-1]
        current_char = input_str[ptr]
        # 打印当前状态
        stack_str = ''.join(stack)
        input_remain = input_str[ptr:]
        print(f"{step}\t\t{stack_str}\t\t{input_remain}\t\t", end='')

        if top == '#' and current_char == '#':
            print("分析成功")
            return True
        if top == current_char:
            # 匹配终结符
            stack.pop()
            ptr += 1
            print(f"匹配{current_char}")
        elif top in productions:
            # 非终结符，查预测分析表
            if current_char in predict_table[top]:
                prod = predict_table[top][current_char]
                print(f"使用{top}→{prod}")
                stack.pop()
                if prod != 'ε':
                    # 反序入栈
                    for c in reversed(prod):
                        stack.append(c)
            else:
                print("出错：无匹配产生式")
                return False
        else:
            print("出错：栈顶符号不匹配")
            return False
        step += 1
    return False


# 测试输入
test_input = "i+i*i"
print(f"分析输入串：{test_input}")
ll1_analysis(test_input)